package MAIN;
//笔试强训第22天
//选择题
/*对于存取指定序号的元素和在最后进行插入和删除运算，用数组最合适，数组取元素O(1)
* 在数组末尾的插入和删除O(1)*/
/*记忆功能：浏览器的回退功能，文本编辑器的撤销操作都是记忆功能，数据结构具有记忆功能
的是栈，栈是先进后出的，就好像记住了所有元素的位置顺序调换一样*/
/*对于循环队列：要浪费一个空间用来判断队列是否已满，如：数组长度为m，能存储元素的个数就是m-1
* 最终判断是否为满，end1 == （end2 + 1）mod m  判断队列是否为空： end1 == end2 */
/*对递归程序的优化通常采用的是尾递归优化，如：在快速排序和归并排序，在递归的终止条件，L是区间
* 最左侧，R是区间最右侧，
* //终止条件
* (L >= R) {
*   return;
* }   然后可以在递归终止处进行优化，当区间个数较小时，采用插入排序来优化，(R - L <= 15)
* 此时就采用插入排序，所以尾递归优化就是在递归条件终止处进行优化*/
/*二叉树结论：根节点从1开始编号，设父亲节点编号为x，left = 2*x，right = 2 * x + 1
* 设现在孩子系欸但编号为n，父亲节点编号就是x / 2
* 如果根节点从0号开始进行编号，在编号为1的基础上增加一个偏移量即可*/
/*在队列这张数据结构中，用到的遍历方法只有层序遍历，前中后序遍历都是借助栈这个结构*/
/*topK问题：在一组数据中，找到前K大（小）的元素，此时用的排序是堆排序/优先级队列
*/
/*在排序算法中，每次经过一次元素的交换就会产生新的逆序的是：快速排序
* 数组的逆序：每当一次元素交换后，当前元素之后还有比当前元素还小的元素，就构成了
* 一次逆序。      冒泡排序：交换相邻的元素，不一定会产生逆序对，插入排序和选择排序
* 都是在和是的位置进行插入元素，因此会减少逆序对*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
//编程题
public class Main22 {
    public static void main(String[] args) {
        int a = 20 % 30;
        System.out.println(a);
    }
    //小易的升级之路（打boss）
    public static void main2(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            int num = scan.nextInt();
            int power = scan.nextInt();
            int[] arr = new int[num];
            for (int i = 0; i < num; i++) {
                arr[i] = scan.nextInt();
            }
            for (int i = 0; i < num; i++) {
                if (power >= arr[i]) {
                    power += arr[i];
                }else {
                    power += gdc(power,arr[i]);
                }
            }
            System.out.println(power);
        }
    }
    //求最大公约数
    public static int gdc(int a, int b) {
        int c = a % b;
        while ((c = a % b) != 0) {
            a = b;
            b = c;
        }
        return b;
    }
    //找出字符串中第一个只出现一次的字符
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String s1 = scan.nextLine();
            String s2 = s1.toLowerCase();
            int[] count = new int[123];
            for (int i = 0; i < count.length; i++) {
                count[s2.charAt(i)]++;
            }
            for (int i = 0; i < count.length; i++) {
                if (count[s2.charAt(i)] == 1) {
                    System.out.println(count[i]);
                }
            }
        }
    }
}

